﻿//快速排序hoare版本(1)
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;
	int key = left++;

	while (left <= right)
	{
		while (left <= right && arr[right] > arr[key])
		{
			right--;
		}
		while (left <= right && arr[left] < arr[key])
		{
			left++;
		}

		if (left <= right)
		{
			swap(&arr[left++], &arr[right--]);
		}
	}
	swap(&arr[key], &arr[right]);

	quicksort(arr, begin, right - 1);
	quicksort(arr, right + 1, end);
}(1)
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;

	int key = left++;

	while (left <= right)
	{
		while (left <= right && arr[right] > arr[key])
		{
			right--;
		}
		while (left <= right && arr[left] < arr[key])
		{
			left++;
		}

		if (left <= right)
		{
			swap(&arr[left++], &arr[right--]);
		}
	}
	swap(&arr[key], &arr[right]);

	quicksort(arr, begin, right - 1);
	quicksort(arr, right + 1, end);
}